import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 120. 三角形最小路径和
 * https://leetcode-cn.com/problems/triangle/submissions/
 */
public class Solutions_120 {
    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<>();
        triangle.add(Arrays.asList(2));
        triangle.add(Arrays.asList(3, 4));
        triangle.add(Arrays.asList(6, 5, 7));
        triangle.add(Arrays.asList(4, 1, 8, 3));  // output: 11  {2, 3, 5, 1}

        int result = minimumTotal2(triangle);
        System.out.println(result);
    }

    /**
     * 解法一：动态规划：自顶向下
     */
    public static int minimumTotal(List<List<Integer>> triangle) {
        // 空值与行数为 0 的判断
        if (triangle == null || triangle.size() < 1) {
            return 0;
        }
        int row = triangle.size();
        // dp[2][0] = 9, 表示第 triangle 的第 3 行的第 1 个位置上，从顶部的路径值相加得到的最小值是 9
        int[][] dp = new int[row][row];
        // 第一行第一个元素作为 dp 数组的默认值
        dp[0][0] = triangle.get(0).get(0);

        for (int i = 1; i < row; i++) {
            List<Integer> curRow = triangle.get(i);
            for (int j = 0; j <= i; j++) {
                // 每个元素，比较上一层中索引 - 1，与相同索引上的数中的最小值并相加
                if (j == 0) {
                    dp[i][j] = dp[i - 1][j] + curRow.get(j);
                } else if (j == i) {
                    // 不是第一个及最后一个元素时，有相邻的元素
                    dp[i][j] = dp[i - 1][j - 1] + curRow.get(j);
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + curRow.get(j);
                }
            }
        }
        // 遍历最后一行，得到最小值
        int res = dp[row - 1][0];
        for (int num : dp[row - 1]) {
            res = Math.min(res, num);
        }
        return res;
    }

    /**
     * 解法二：动态规划：自底向上
     */
    public static int minimumTotal2(List<List<Integer>> triangle) {
        // 空值与行数为 0 的判断
        if (triangle == null || triangle.size() < 1) {
            return 0;
        }
        int row = triangle.size();
        // dp[2] = 9, 表示第 triangle 的第 1 行的第 1 个位置上，从底部元素相加得到的最小值是 9
        int[] dp = new int[row];
        // 最后一行作为 dp 数组的默认值
        for (int i = 0; i < row; i++) {
            dp[i] = triangle.get(row - 1).get(i);
        }

        for (int i = row - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                // 每个元素，比较下一层中相同索引及 索引 + 1 上的数中的最小值并相加
                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
            }
        }
        // 最终的顶部节点值，一定是路径总和最小的
        return dp[0];
    }
}
